/*
 * contrib/intarray/_int_tool.c
 */
#include "postgres.h"

#include <limits.h>

#include "_int.h"
#include "catalog/pg_type.h"
#include "lib/qunique.h"

/* 参数假定为已排序且唯一 */
bool inner_int_contains(ArrayType *fc_a, ArrayType *fc_b)
{
	int			fc_na,
				fc_nb;
	int			fc_i,
				fc_j,
				fc_n;
	int		   *fc_da,
			   *fc_db;

	fc_na = ARRNELEMS(fc_a);
	fc_nb = ARRNELEMS(fc_b);
	fc_da = ARRPTR(fc_a);
	fc_db = ARRPTR(fc_b);

	fc_i = fc_j = fc_n = 0;
	while (fc_i < fc_na && fc_j < fc_nb)
	{
		if (fc_da[fc_i] < fc_db[fc_j])
			fc_i++;
		else if (fc_da[fc_i] == fc_db[fc_j])
		{
			fc_n++;
			fc_i++;
			fc_j++;
		}
		else
			break;				/* db[j] 不在 da 中 */
	}

	return (fc_n == fc_nb);
}

/* 参数假定为已排序 */
bool inner_int_overlap(ArrayType *fc_a, ArrayType *fc_b)
{
	int			fc_na,
				fc_nb;
	int			fc_i,
				fc_j;
	int		   *fc_da,
			   *fc_db;

	fc_na = ARRNELEMS(fc_a);
	fc_nb = ARRNELEMS(fc_b);
	fc_da = ARRPTR(fc_a);
	fc_db = ARRPTR(fc_b);

	fc_i = fc_j = 0;
	while (fc_i < fc_na && fc_j < fc_nb)
	{
		if (fc_da[fc_i] < fc_db[fc_j])
			fc_i++;
		else if (fc_da[fc_i] == fc_db[fc_j])
			return true;
		else
			fc_j++;
	}

	return false;
}

ArrayType * inner_int_union(ArrayType *fc_a, ArrayType *fc_b)
{
	ArrayType  *fc_r = NULL;

	CHECKARRVALID(fc_a);
	CHECKARRVALID(fc_b);

	if (ARRISEMPTY(fc_a) && ARRISEMPTY(fc_b))
		return new_intArrayType(0);
	if (ARRISEMPTY(fc_a))
		fc_r = copy_intArrayType(fc_b);
	if (ARRISEMPTY(fc_b))
		fc_r = copy_intArrayType(fc_a);

	if (!fc_r)
	{
		int			fc_na = ARRNELEMS(fc_a),
					fc_nb = ARRNELEMS(fc_b);
		int		   *fc_da = ARRPTR(fc_a),
				   *fc_db = ARRPTR(fc_b);
		int			fc_i,
					fc_j,
				   *fc_dr;

		fc_r = new_intArrayType(fc_na + fc_nb);
		fc_dr = ARRPTR(fc_r);

		/* 联合 */
		fc_i = fc_j = 0;
		while (fc_i < fc_na && fc_j < fc_nb)
		{
			if (fc_da[fc_i] == fc_db[fc_j])
			{
				*fc_dr++ = fc_da[fc_i++];
				fc_j++;
			}
			else if (fc_da[fc_i] < fc_db[fc_j])
				*fc_dr++ = fc_da[fc_i++];
			else
				*fc_dr++ = fc_db[fc_j++];
		}

		while (fc_i < fc_na)
			*fc_dr++ = fc_da[fc_i++];
		while (fc_j < fc_nb)
			*fc_dr++ = fc_db[fc_j++];

		fc_r = resize_intArrayType(fc_r, fc_dr - ARRPTR(fc_r));
	}

	if (ARRNELEMS(fc_r) > 1)
		fc_r = _int_unique(fc_r);

	return fc_r;
}

ArrayType * inner_int_inter(ArrayType *fc_a, ArrayType *fc_b)
{
	ArrayType  *fc_r;
	int			fc_na,
				fc_nb;
	int		   *fc_da,
			   *fc_db,
			   *fc_dr;
	int			fc_i,
				fc_j,
				fc_k;

	if (ARRISEMPTY(fc_a) || ARRISEMPTY(fc_b))
		return new_intArrayType(0);

	fc_na = ARRNELEMS(fc_a);
	fc_nb = ARRNELEMS(fc_b);
	fc_da = ARRPTR(fc_a);
	fc_db = ARRPTR(fc_b);
	fc_r = new_intArrayType(Min(fc_na, fc_nb));
	fc_dr = ARRPTR(fc_r);

	fc_i = fc_j = fc_k = 0;
	while (fc_i < fc_na && fc_j < fc_nb)
	{
		if (fc_da[fc_i] < fc_db[fc_j])
			fc_i++;
		else if (fc_da[fc_i] == fc_db[fc_j])
		{
			if (fc_k == 0 || fc_dr[fc_k - 1] != fc_db[fc_j])
				fc_dr[fc_k++] = fc_db[fc_j];
			fc_i++;
			fc_j++;
		}
		else
			fc_j++;
	}

	if (fc_k == 0)
	{
		pfree(fc_r);
		return new_intArrayType(0);
	}
	else
		return resize_intArrayType(fc_r, fc_k);
}

void rt__int_size(ArrayType *fc_a, float *fc_size)
{
	*fc_size = (float) ARRNELEMS(fc_a);
}

/* qsort_arg 比较函数用于 isort() */
static int fc_isort_cmp(const void *fc_a, const void *fc_b, void *fc_arg)
{
	int32		fc_aval = *((const int32 *) fc_a);
	int32		fc_bval = *((const int32 *) fc_b);

	if (fc_aval < fc_bval)
		return -1;
	if (fc_aval > fc_bval)
		return 1;

	/*
	 * 报告是否有任何重复项。如果存在相等的键，qsort 必须
	 * 在某个时候进行比较，否则它无法知道谁应该
	 * 位于另一个之前或之后。
	 */
	*((bool *) fc_arg) = true;
	return 0;
}

/* 对给定的数据进行排序（len >= 2）。如果发现任何重复项，返回 true */
bool isort(int32 *fc_a, int fc_len)
{
	bool		fc_r = false;

	qsort_arg(fc_a, fc_len, sizeof(int32), fc_isort_cmp, (void *) &fc_r);
	return fc_r;
}

/* 创建一个新的整数数组，长度为 "num" 个元素 */
ArrayType * new_intArrayType(int fc_num)
{
	ArrayType  *fc_r;
	int			fc_nbytes;

	/* 如果没有元素，返回一个零维数组 */
	if (fc_num <= 0)
	{
		Assert(fc_num == 0);
		fc_r = construct_empty_array(INT4OID);
		return fc_r;
	}

	fc_nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * fc_num;

	fc_r = (ArrayType *) palloc0(fc_nbytes);

	SET_VARSIZE(fc_r, fc_nbytes);
	ARR_NDIM(fc_r) = 1;
	fc_r->dataoffset = 0;			/* 表示没有空位图的标记 */
	ARR_ELEMTYPE(fc_r) = INT4OID;
	ARR_DIMS(fc_r)[0] = fc_num;
	ARR_LBOUND(fc_r)[0] = 1;

	return fc_r;
}

ArrayType * resize_intArrayType(ArrayType *fc_a, int fc_num)
{
	int			fc_nbytes;
	int			fc_i;

	/* 如果没有元素，返回一个零维数组 */
	if (fc_num <= 0)
	{
		Assert(fc_num == 0);
		fc_a = construct_empty_array(INT4OID);
		return fc_a;
	}

	if (fc_num == ARRNELEMS(fc_a))
		return fc_a;

	fc_nbytes = ARR_DATA_OFFSET(fc_a) + sizeof(int) * fc_num;

	fc_a = (ArrayType *) repalloc(fc_a, fc_nbytes);

	SET_VARSIZE(fc_a, fc_nbytes);
	/* 通常数组应该已经是 1-D，但以防万一 ... */
	for (fc_i = 0; fc_i < ARR_NDIM(fc_a); fc_i++)
	{
		ARR_DIMS(fc_a)[fc_i] = fc_num;
		fc_num = 1;
	}
	return fc_a;
}

ArrayType * copy_intArrayType(ArrayType *fc_a)
{
	ArrayType  *fc_r;
	int			fc_n = ARRNELEMS(fc_a);

	fc_r = new_intArrayType(fc_n);
	memcpy(ARRPTR(fc_r), ARRPTR(fc_a), fc_n * sizeof(int32));
	return fc_r;
}

/* 压缩键的 num */
int internal_size(int *fc_a, int fc_len)
{
	int			fc_i;
	int64		fc_size = 0;

	for (fc_i = 0; fc_i < fc_len; fc_i += 2)
	{
		if (!fc_i || fc_a[fc_i] != fc_a[fc_i - 1]) /* 不计算重复范围 */
			fc_size += (int64) (fc_a[fc_i + 1]) - (int64) (fc_a[fc_i]) + 1;
	}

	if (fc_size > (int64) INT_MAX || fc_size < (int64) INT_MIN)
		return -1;				/* 上溢 */
	return (int) fc_size;
}

/* 就地唯一化 r 的元素 ... r 必须已经排序 */
ArrayType * _int_unique(ArrayType *fc_r)
{
	int			fc_num = ARRNELEMS(fc_r);
	bool		fc_duplicates_found;	/* 未使用 */

	fc_num = qunique_arg(ARRPTR(fc_r), fc_num, sizeof(int), fc_isort_cmp,
					  &fc_duplicates_found);

	return resize_intArrayType(fc_r, fc_num);
}

void gensign(BITVECP fc_sign, int *fc_a, int fc_len, int fc_siglen)
{
	int			fc_i;

	/* 我们假设符号向量之前已被清零 */
	for (fc_i = 0; fc_i < fc_len; fc_i++)
	{
		HASH(fc_sign, *fc_a, fc_siglen);
		fc_a++;
	}
}

int32 intarray_match_first(ArrayType *fc_a, int32 fc_elem)
{
	int32	   *fc_aa,
				fc_c,
				fc_i;

	CHECKARRVALID(fc_a);
	fc_c = ARRNELEMS(fc_a);
	fc_aa = ARRPTR(fc_a);
	for (fc_i = 0; fc_i < fc_c; fc_i++)
		if (fc_aa[fc_i] == fc_elem)
			return (fc_i + 1);
	return 0;
}

ArrayType * intarray_add_elem(ArrayType *fc_a, int32 fc_elem)
{
	ArrayType  *fc_result;
	int32	   *fc_r;
	int32		fc_c;

	CHECKARRVALID(fc_a);
	fc_c = ARRNELEMS(fc_a);
	fc_result = new_intArrayType(fc_c + 1);
	fc_r = ARRPTR(fc_result);
	if (fc_c > 0)
		memcpy(fc_r, ARRPTR(fc_a), fc_c * sizeof(int32));
	fc_r[fc_c] = fc_elem;
	return fc_result;
}

ArrayType * intarray_concat_arrays(ArrayType *fc_a, ArrayType *fc_b)
{
	ArrayType  *fc_result;
	int32		fc_ac = ARRNELEMS(fc_a);
	int32		fc_bc = ARRNELEMS(fc_b);

	CHECKARRVALID(fc_a);
	CHECKARRVALID(fc_b);
	fc_result = new_intArrayType(fc_ac + fc_bc);
	if (fc_ac)
		memcpy(ARRPTR(fc_result), ARRPTR(fc_a), fc_ac * sizeof(int32));
	if (fc_bc)
		memcpy(ARRPTR(fc_result) + fc_ac, ARRPTR(fc_b), fc_bc * sizeof(int32));
	return fc_result;
}

ArrayType * int_to_intset(int32 fc_n)
{
	ArrayType  *fc_result;
	int32	   *fc_aa;

	fc_result = new_intArrayType(1);
	fc_aa = ARRPTR(fc_result);
	fc_aa[0] = fc_n;
	return fc_result;
}

int compASC(const void *fc_a, const void *fc_b)
{
	if (*(const int32 *) fc_a == *(const int32 *) fc_b)
		return 0;
	return (*(const int32 *) fc_a > *(const int32 *) fc_b) ? 1 : -1;
}

int compDESC(const void *fc_a, const void *fc_b)
{
	if (*(const int32 *) fc_a == *(const int32 *) fc_b)
		return 0;
	return (*(const int32 *) fc_a < *(const int32 *) fc_b) ? 1 : -1;
}
